// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

func main() {
	array := []int{1, 6, 8}
	//调用 minScoreTriangulation() 函数计算最小分数
	result := minScoreTriangulation(array)
	fmt.Println(result)
}

func minScoreTriangulation(values []int) int {
	n := len(values)
	//创建一个二维切片来存储三角化子问题的最小分数
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	//计算增加子问题大小的最小分数
	for length := 3; length <= n; length++ {
		//遍历给定大小的所有可能的子数组
		for i := 0; i <= n-length; i++ {
			j := i + length - 1      //子数组的结束索引
			dp[i][j] = math.MaxInt32 //将最小分数初始化为最大整数值
			//遍历子数组的所有可能拆分
			for k := i + 1; k < j; k++ {
				//计算由顶点i、j、k组成的三角形的分数，将其加到两个子问题的最小分数上
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+values[i]*values[j]*values[k])
			}
		}
	}

	return dp[0][n-1]
}

// 计算两个整数中最小值的函数
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

//$ go run interview12-5.go
//48
